package Chapter1.sort;

public class FastSort {
    public static void main(String[] args) {
        int nums[] = {1, 5, 3, 2, 4};
        fastSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }


    public static int partition(int[] nums, int low, int high) {
        int pivot = nums[low];
        int i = low + 1, j = high;
        while (i <= j) {
            while (i < high && nums[i] <= pivot) {
                i++;
            }
            while (j > low && nums[j] >= pivot) {
                j--;
            }
            if (i >= j) {
                break;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        int temp = nums[low];
        nums[low] = nums[j];
        nums[j] = temp;
        return j;
    }

    public static void fastSort(int[] nums, int low, int high) {
        if (low < high) {
            int partition = partition(nums, low, high);
            fastSort(nums, low, partition - 1);
            fastSort(nums, partition + 1, high);
        }

    }
}
